//求子集二（给定集合中含重复元素，要求无重复子集） 力扣90
//回溯算法 收集每一个节点作为答案 树层去重（使用used数组）
class Solution {
public:
	vector<vector<int>> ans;
	vector<int> path;
	vector<bool> used = vector<bool>(12);
	void backtracking(vector<int> nums,int startindex)
	{
		ans.push_back(path);
		for(int i = startindex; i < nums.size(); i++)
		{
			if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;
			path.push_back(nums[i]);
			used[i] = true;
			backtracking(nums,i+1);
			path.pop_back();
			used[i] = false;
		}
	}
	vector<vector<int>> subsetsWithDup(vector<int>& nums) {
		sort(nums.begin(),nums.end());
		backtracking(nums,0);
		return ans;
		
	}
};
